package ar.uba.fi.tonyvaliente.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Set;

public abstract class BPlusTree<K extends Comparable<K>, V> implements Iterable<K> {
	protected int elementsPerNode;
	protected BPlusTreeNodeReference<K, V> rootNodeReference;
	protected Set<BPlusTreeNodeReference<K, V>> dirtyNodeReferences = new HashSet<BPlusTreeNodeReference<K, V>>();

	protected abstract BPlusTreeNodeReference<K, V> createReference();
	
	public void add(K key, V value) throws BPlusTreeException {
		BPlusTreeNode<K, V>.AddResult result = this.getRootNodeReference().getNode().add(key, value);
		if (result != null) {
			InnerBPlusTreeNode<K, V> newRootNode = new InnerBPlusTreeNode<K, V>(this, null);
			newRootNode.getKeys().add(result.getKey());
			newRootNode.getReferences().add(0, result.getLeftReference());
			newRootNode.getReferences().add(1, result.getRightReference());

			BPlusTreeNodeReference<K, V> newRootReference = this.createReference();
			newRootReference.setNode(newRootNode);
			this.setRootNodeReference(newRootReference);
			this.addDirtyNodeReference(newRootReference);
			
			result.getLeftReference().getNode().setParentReference(newRootReference);
			this.addDirtyNodeReference(result.getLeftReference());
			result.getRightReference().getNode().setParentReference(newRootReference);
			this.addDirtyNodeReference(result.getRightReference());
		}
		
		for (BPlusTreeNodeReference<K, V> reference : this.dirtyNodeReferences) {
			if (reference != null) {
				reference.updateNode();
			}
		}
		this.dirtyNodeReferences.clear();
	}
	
	public V get(K key) throws BPlusTreeException, NoSuchElementException {
		return this.getRootNodeReference().getNode().get(key);
	}

	public int getElementsPerNode() {
		return this.elementsPerNode;
	}

	protected void setElementsPerNode(int elementsPerNode) {
		this.elementsPerNode = elementsPerNode;
	}
	
	protected BPlusTreeNodeReference<K, V> getRootNodeReference() throws BPlusTreeException {
		return this.rootNodeReference;
	}

	protected void setRootNodeReference(BPlusTreeNodeReference<K, V> rootNodeReference) throws BPlusTreeException {
		this.rootNodeReference = rootNodeReference;
	}
	
	protected void addDirtyNodeReference(BPlusTreeNodeReference<K, V> dirtyReference) {
		this.dirtyNodeReferences.add(dirtyReference);
	}
	
	public abstract void close() throws BPlusTreeException;

	public Iterator<K> iterator() {
		try {
			return new BPlusTreeIterator(this);
		} catch (BPlusTreeException e) {
			e.printStackTrace();
		}
		return new ArrayList<K>().iterator();
	}
	
	protected class BPlusTreeIterator implements Iterator<K> {
		private BPlusTree<K, V> tree;
		private LeafBPlusTreeNode<K, V> currentNode;
		private List<K> currentKeys;
		private int currentIndex;
		private boolean hasNext;
		
		public BPlusTreeIterator(BPlusTree<K, V> tree) throws BPlusTreeException {
			this.setTree(tree);
			this.setCurrentNode(this.getNextNode());
		}

		@Override
		public boolean hasNext() {
			return this.getHasNext();
		}

		@Override
		public K next() {
			K next = null;
			int index = this.getCurrentIndex();
			List<K> currentKeys = this.getCurrentKeys();
			
			if (index < currentKeys.size() - 1) {
				next = currentKeys.get(index);
				this.setCurrentIndex(++index);
				this.setHasNext(true);
			} else if (index == currentKeys.size() - 1) {
				next = currentKeys.get(index);
				this.setHasNext(false);
				try {
					this.setCurrentNode(this.getNextNode());
				} catch (BPlusTreeException e) {
					e.printStackTrace();
				}
			}

			return next;
		}

		@Override
		public void remove() {
			throw new UnsupportedOperationException("1");
		}

		private BPlusTree<K, V> getTree() {
			return this.tree;
		}
		private void setTree(BPlusTree<K, V> tree) {
			this.tree = tree;
		}

		private LeafBPlusTreeNode<K, V> getNextNode() throws BPlusTreeException
		{
			LeafBPlusTreeNode<K, V> currentNode = this.getCurrentNode();
			if (currentNode == null) {
				BPlusTreeNode<K, V> node = this.getTree().getRootNodeReference().getNode();
				while (node instanceof InnerBPlusTreeNode) {
					InnerBPlusTreeNode<K, V> innerNode = (InnerBPlusTreeNode<K, V>)node;
					node = innerNode.getReferences().get(0).getNode();
				}
				currentNode = (LeafBPlusTreeNode<K, V>)node;
				LeafBPlusTreeNode<K, V> dummyNode = new LeafBPlusTreeNode<K, V>(this.getTree(), null);
				BPlusTreeNodeReference<K, V> dummyReference = this.getTree().createReference();
				dummyReference.setNode(currentNode);
				dummyNode.setNextReference(dummyReference);
				currentNode = dummyNode;
			}
			while (true) {
				BPlusTreeNodeReference<K, V> nextReference = currentNode.getNextReference();
				if (nextReference == null)
					break;
					
				LeafBPlusTreeNode<K, V> nextNode = null;
				try {
					nextNode = (LeafBPlusTreeNode<K, V>)nextReference.getNode();
				} catch (BPlusTreeException e) {
					e.printStackTrace();
				}
				if (nextNode == null)
					break;
				
				currentNode = nextNode;
				if (currentNode.getData().size() > 0) {
					return currentNode;
				}

				currentNode = nextNode;
			}
			
			return null;
		}

		private List<K> getCurrentKeys() {
			return this.currentKeys;
		}

		private void setCurrentKeys(List<K> keys) {
			this.currentKeys = keys;
			if (this.currentKeys != null) {
				Collections.sort(this.currentKeys);
				this.setCurrentIndex(0);
				this.setHasNext(true);
			}
		}
		
		private int getCurrentIndex() {
			return this.currentIndex;
		}
		
		private void setCurrentIndex(int currentIndex) {
			this.currentIndex = currentIndex;
		}

		private LeafBPlusTreeNode<K, V> getCurrentNode() {
			return this.currentNode;
		}

		private void setCurrentNode(LeafBPlusTreeNode<K, V> node) {
			this.currentNode = node;
			if (this.currentNode != null) {
				this.setCurrentKeys(new ArrayList<K>(node.getData().keySet()));
			} else {
				this.setCurrentKeys(null);
			}
		}
		
		private boolean getHasNext() {
			return this.hasNext;
		}

		private void setHasNext(boolean hasNext) {
			this.hasNext = hasNext;
		}
	}
	
	public void validate() throws BPlusTreeException {
		BPlusTreeNode<K, V> rootNode = this.getRootNodeReference().getNode();
		rootNode.validate();
		
		Queue<BPlusTreeNodeReference<K, V>> queue1 = new LinkedList<BPlusTreeNodeReference<K, V>>();
		queue1.offer(this.getRootNodeReference());
		while (queue1.size() > 0) {
			BPlusTreeNodeReference<K, V> reference = queue1.poll();
			BPlusTreeNode<K, V> node = reference.getNode();
			
			if (node instanceof InnerBPlusTreeNode) {
				InnerBPlusTreeNode<K, V> innerNode = (InnerBPlusTreeNode<K, V>)node;
				List<K> keys = innerNode.getKeys();
				List<BPlusTreeNodeReference<K, V>> references = innerNode.getReferences();
			
				for (int i = 0; i < keys.size(); i++) {
					K parentKey = keys.get(i);
					
					Queue<BPlusTreeNodeReference<K, V>> queue2 = new LinkedList<BPlusTreeNodeReference<K, V>>();

					queue2.offer(references.get(i));
					while (queue2.size() > 0) {
						BPlusTreeNodeReference<K, V> leftReference = queue2.poll();
						BPlusTreeNode<K, V> leftNode = leftReference.getNode();
						innerNode.validateLeftChild(parentKey, leftNode);

						if(leftNode instanceof InnerBPlusTreeNode)
						{
							InnerBPlusTreeNode<K, V> leftInnerNode = (InnerBPlusTreeNode<K, V>)leftNode;
							for (BPlusTreeNodeReference<K, V> innerLeftReference : leftInnerNode.getReferences()) {
								queue2.offer(innerLeftReference);			
							}
						}
					}
					
					queue2.offer(references.get(i + 1));
					while (queue2.size() > 0) {
						BPlusTreeNodeReference<K, V> rightReference = queue2.poll();
						BPlusTreeNode<K, V> rightNode = rightReference.getNode();
						innerNode.validateRightChild(parentKey, rightNode);

						if(rightNode instanceof InnerBPlusTreeNode)
						{
							InnerBPlusTreeNode<K, V> rightInnerNode = (InnerBPlusTreeNode<K, V>)rightNode;
							for (BPlusTreeNodeReference<K, V> innerRightReference : rightInnerNode.getReferences()) {
								queue2.offer(innerRightReference);			
							}
						}
					}
				}
			
				for (BPlusTreeNodeReference<K, V> innerReference : innerNode.getReferences()) {
					queue1.offer(innerReference);			
				}
			}
		}
	}
}
